# 你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。
#
#  示例 1:
#
#  输入: [4, 1, 8, 7]
# 输出: True
# 解释: (8-4) * (7-1) = 24
#
#
#  示例 2:
#
#  输入: [1, 2, 1, 2]
# 输出: False
#
#
#  注意:
#
#
#  除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。
#  每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如，[1, 1, 1, 1] 作为输入时，表达式 -1 - 1 - 1 - 1 是不允
# 许的。
#  你不能将数字连接在一起。例如，输入为 [1, 2, 1, 2] 时，不能写成 12 + 12 。
#
#  Related Topics 深度优先搜索
#  👍 218 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
from typing import List


class Solution:
    def judgePoint24(self, nums: List[int]) -> bool:
        if len(nums) == 1:
            return True if abs(nums[0] - 24) < 0.001 else False

        # 每次选两个数字做运算，把结果丢入 数组，继续遍历

        for i in range(0, len(nums)):
            for j in range(i + 1, len(nums)):

                first = nums[i]
                second = nums[j]

                rest = nums[:]

                # 先 pop 后面的元素 不影响 i 的下标
                rest.pop(j)
                rest.pop(i)

                # 加法
                res = first + second

                if self.judgePoint24([res] + rest):
                    return True

                # 除法
                if second != 0:

                    res = first / second

                    if self.judgePoint24([res] + rest):
                        return True

                if first != 0:
                    res = second / first

                    if self.judgePoint24([res] + rest):
                        return True

                # 乘法
                res = first * second

                if self.judgePoint24([res] + rest):
                    return True

                # 减法
                res = first - second

                if self.judgePoint24([res] + rest):
                    return True

                if self.judgePoint24([-res] + rest):
                    return True

        return False

    # leetcode submit region end(Prohibit modification and deletion)


print(Solution().judgePoint24([4, 1, 8, 7]))
